package com.mingweicai.intergration.sort;

import java.util.Comparator;
import java.util.PriorityQueue;

public class HeadSort {

  public static void main(String args[]){
    int arr[] = new int[]{6,5,4,3,1};
    arr = headSort(arr);
    for(int i=0; i<arr.length; i++){
      System.out.print(arr[i] + " ");
    }

    PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
      @Override
      public int compare(Integer o1, Integer o2) {
        return o1 - o2;
      }
    });

    queue.add(1);
    queue.add(2);

    queue.forEach((i) -> System.out.println(i));
  }

  private static int[] headSort(int[] arr){
    int n = arr.length;
    for(int i=n/2 - 1; i>=0; i--){
      headAdjust(arr,i,n-1);
    }
    for(int i=n-1; i>0; i--){
      swap(arr,0,i);
      headAdjust(arr,0,i-1);
    }
    return arr;
  }

  private static void headAdjust(int[] arr, int s, int m){
    int temp = arr[s];
    for(int j=2*s; j<=m; j*=2){
      if(j+1<=m && arr[j] < arr[j+1]){
        j=j+1;
      }
      if(temp >= arr[j]){
        break;
      }
      arr[s] = arr[j];
      s = j;
    }
    arr[s] = temp;
  }

  private static void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}
